#include <iostream>
#include <vector>
#include <algorithm>
#include <stack>
using namespace std;

int GetRandom(vector<int>& arr, int l, int r)
{
	int index = l + rand() % (r - l + 1);
	return arr[index];
}

void QuickSort(vector<int>& arr, int l, int r)
{
	if (l >= r) return;
	int key = GetRandom(arr, l, r);
	int left = l - 1, right = r + 1, cur = l;
	while (cur < right)
	{
		if (arr[cur] > key)
			swap(arr[cur], arr[--right]);
		else if (arr[cur] < key)
			swap(arr[cur++], arr[++left]);
		else
			cur++;
	}
	// [l, left] [left + 1, right - 1] [right, r]
	QuickSort(arr, l, left);
	QuickSort(arr, right, r);
}


int PartSort(vector<int>& arr, int left, int right)
{
	int end = left, cur = left + 1, key = arr[left];
	while (cur <= right)
	{
		if (arr[cur] < key)
			swap(arr[++end], arr[cur]);
		cur++;
	}
	swap(arr[left], arr[end]);
	return end;
}

void QuickSort(vector<int>& arr)
{
	stack<pair<int, int>> st;
	st.push(make_pair(0, arr.size() - 1));
	while (st.size())
	{
		auto kv = st.top(); st.pop();
		int left = kv.first, right = kv.second;
		int keyi = PartSort(arr, left, right);
		if (left < keyi - 1)
			st.push(make_pair(left, keyi - 1));
		if (right > keyi + 1)
			st.push(make_pair(keyi + 1, right));
	}
}

int main()
{
	vector<int> v = { 1, 43, 2 ,2, 3, 343, 3434, 2, 2322, 3, 788 };
	QuickSort(v);

	for (auto x : v)
		std::cout << x << " ";
	std::cout << std::endl;
	return 0;
}